package com.itcam.sort.countingsort;

import java.util.Arrays;

/**
 * @author : Cammy.Wu
 * Description : 计数排序
 */

public class CountingSort {
    public static void main(String[] args) {
        int[] a = {9, 5, 7, 7, 1, -7};
        System.out.println(Arrays.toString(a));
        countingSort(a);
        System.out.println(Arrays.toString(a));
    }

    /*
        {9, 5, 7, 7, 1, -7}  a
        [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1] count
         0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 索引数
         -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7  8  9 实际数值
     */
    private static void countingSort(int[] a) {
        int max = a[0];
        int min = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
            if (a[i] < min) {
                min = a[i];
            }
        }
        int[] count = new int[max - min + 1];
        for (int v : a) {
            count[v - min]++;
        }
        System.out.println(Arrays.toString(count));
        int j = 0;
        for (int i = 0; i < count.length; i++) {
            // i代表原始数组元素 count[i] 元素出现次数
            // i + min 代表原始数组元素 count[i] 元素出现次数
            while (count[i] > 0) {
                a[j++] = i + min;
                count[i]--; // count[i]-- 减少一个元素
            }
        }
    }
}
